It is often desired to construct a cross-sectional view (layer or slice) and/or three dimensional (3D) view of an object for which actually presenting such views is impossible, such as due to irreparably damaging the object. For example, imaging systems are utilized in the medical arts to provide a view of a slice through a living human's body and to provide 3D views of organs therein. Similarly, imaging systems are utilized in the manufacture and inspection of industrial products, such as electronic circuit boards and/or components, to provide layer views and 3D views for inspection thereof.
Often desired images are provided through reconstruction techniques which use multiple two-dimensional (2D) radiographic, e.g., X band radiation (X-ray), images, e.g., detector images. The technique of reconstructing a desired image or view of an object (be it a 3D image, a cross-sectional image, and/or the like) from multiple projections (e.g., different detector images) is broadly referred to as tomography. When such reconstructing of a cross-sectional image is performed with the aid of a processor-based device (or “computer”), the technique is broadly referred to as computed (or computerized) tomography (CT). In a typical example application, a radiation source projects X band radiation through an object onto an electronic sensor array thereby providing a detector image. By providing relative movement between one or more of the object, the source, and the sensor array, multiple views (multiple detector images having different perspectives) may be obtained. An image of a slice through the object or a three-dimensional (“3D”) image of the object may then be approximated by use of proper mathematical transforms of the multiple views. That is, cross-sectional images of an object may be reconstructed, and in certain applications such cross-sectional images may be combined to form a 3D image of the object.
Three-dimensional computed tomography has the potential for more accurate image reconstruction than laminography or tomosynthesis, but at the expense of speed (computation time). Three-dimensional computed tomography typically requires many projections, and is computationally intensive. One approach to three-dimensional computer-aided tomography is to position an X-ray source having a cone-shaped three-dimensional ray output on one side of an object to be viewed, position a two-dimensional array of sensors on the opposite side of the object to be viewed, and synchronously move the source/array relative to the object. There are many suitable scan paths. For example, the source may be moved in orthogonal circles around the object to be viewed, or the source may be moved along a helical path or other path along a cylinder surrounding the object to be viewed. This approach, known as “cone-beam tomography,” is preferable in many cases for reconstructing cross-sectional images, and is potentially preferable for industrial inspection systems (e.g., for electronic assembly analysis) because of the resulting image quality.
Perhaps the best known practical application of X-ray absorption tomography is the medical computerized tomography scanner (CT Scanner, also called computer-aided tomography or computerized axial tomography (CAT)). For instance, cross-sectional image reconstruction from radiographic (e.g., X-ray) images is commonly used in medical applications to generate a cross-sectional image (and/or 3D view) of the human body or part of the human body from an X-ray image. In those applications, speed of reconstruction of the cross-sectional images is typically not very important. However, as medical procedures continue to evolve, certain medical applications are beginning to desire fast reconstruction of cross-sectional images. For instance, real-time X-ray imaging is increasingly being desired by medical procedures, such as many electro-physiologic cardiac procedures, peripheral vascular procedures, percutaneous transluminal catheter angioplasty (PTCA) procedures, urological procedures, and orthopedic procedures, as examples.
Tomography is also of interest in automated inspection of industrial products. For instance, reconstruction of cross-sectional images from radiographic (e.g., X-ray) images has been utilized in quality control inspection systems for inspecting a manufactured product, such as electronic devices (e.g., printed circuit boards). That is, tomography may be used in an automated inspection system to reconstruct images of one or more planes (which may be referred to herein as “depth layers” or “cross-sections”) of an object under study in order to evaluate the quality of the object (or portion thereof). An X-ray imaging system may create 2-dimensional detector images (layers, or slices) of a circuit board at various locations and at various orientations. Primarily, one is interested in images which lie in the same plane as the circuit board. In order to obtain these images at a given region of interest, raw X-ray detector images may be mathematically processed using a reconstruction algorithm.
For instance, a printed circuit board (or other object under study) may comprise various depth layers of interest for inspection. As a relatively simple example, a dual-sided printed circuit board may comprise solder joints on both sides of the board. Thus, each side of the circuit board on which the solder joints are arranged may comprise a separate layer of the board. Further, the circuit board may comprise surface mounts (e.g., a ball grid array of solder) on each of its sides, thus resulting in further layers of the board. The object under study may be imaged from various different angles (e.g., by exposure to X-rays at various different angles) resulting in radiographic images of the object, and such radiographic images may be processed to reconstruct an image of a layer (or “slice”) of the object. Thereafter, the resulting cross-sectional image(s) may, in some inspection systems, be displayed layer by layer, and/or such cross-sectional images may be used to reconstruct a full 3D visualization of the object under inspection.
Various mathematical algorithms have been developed for the tomographic reconstruction of images, see e.g., Natterer, et al., “Mathematical Methods in Image Reconstruction”, Society for Industrial and Applied Mathematics, Philadelphia, Pa., 2001, the disclosure of which is incorporated herein by reference. The most popular of these is “Filtered Back-Projection” (FBP), which is a fast, approximate reconstruction method based on the Fourier transform of the projection data. When the projection data is relatively complete i.e., is sampled at a sufficient number of angles and the data is relatively noise-free, this method is both fast and accurate. Medical systems for tomography often meet these criteria, thus leading to the method's popularity. In many medical applications, however, such as X-ray mammography, and in most industrial applications, limitations of speed, accessibility, and/or cost, may reduce the overall coverage and quality of data.
“Limited-Angle Tomography” is a field of tomography comprising methods which attempt to address the above limitations, see e.g., M. E. Davison, “The Ill-Conditioned Nature of the Limited Angle Tomography Problem”, SIAM J. Appl. Math, 43, pp. 428–448, April 1983, and Louis, et al., “Incomplete Data Problems in X-Ray Computerized Tomography II”, Num. Mathematik, 56, pp. 371–383, 1989, the disclosures of which are incorporated herein by reference. Popular reconstruction methods for Limited-Angle Tomography rely on a matrix representation of the Radon Transform, see e.g., Llacer, et al., “Matrix Based Image Reconstruction Methods for Tomography”, IEEE Transactions on Nuclear Science, Vol. NS-32, No. 1, pp. 855–864, February 1985, the disclosure of which is incorporated herein by reference. The Conjugate Gradient method is an iterative solution that has shown some promise in solving the Radon Transform, potentially reducing the computational-burden and reconstruction time considerably, see e.g. Piccolomini, et al., “The Conjugate Gradient Regularization Method in Computed Tomography Problems”, Applied Mathematics and Computation, Vol. 102, Issue 1, pp. 87–99, 1 July 1999; Fessler, et al., “Conjugate-Gradient Preconditioning Methods for Shift-Variant PET Image Reconstruction”, IEEE Transactions on Image Processing, Vol. 8, Issue 5, pp. 688–699, 1999; Kawata, et al., “Constrained Iterative Reconstruction by the Conjugate Gradient Method Measurement Science & Technology”, IEEE Transactions on Medical Imaging, Vol. MI-4, Issue 2, pp. 65–71, 1985; and M. Wang, “Inverse Solutions for Electrical Impedance Tomography Based on Conjugate Gradients Methods”, Measurement Science & Technology Vol. 13, Issue 1, pp. 101–117, 2002; and the above referenced patent application entitled “MAKING 3D CONE-BEAM TOMOGRAPHY FROM ARBITRARY LOCATED X-RAY SOURCES AND IMAGERS BY APPLYING THE CONJUGATE METHOD”, U.S. patent application Ser. No. 10/325,331, filed Dec. 19, 2002, U.S. Publication No. 2004/0120566, published Jun. 24, 2004, the disclosure of which is incorporated herein by reference. It should be noted, however, that because of the fine resolution required by a real-world inspection system, the amount of data that must be processed may be prohibitive.
In a standard cone-beam tomographic reconstruction algorithm, for example, the image data is represented as an array of pixels, where the value of each pixel represents the sampled value of the image at that location. If, for example, 10 projection images are obtained from a detector consisting of 1000×1000 pixels, the total number of rows/columns in a square linear system is 107. It can be readily appreciated that, particularly for large images, the computational cost for computing each pixel in a reconstructed image is prohibitive. Moreover, the amount of computer memory required to store all of the detector images used in the reconstruction of images is prohibitive. In addition, the transmission of such image data, such as along a pipeline within the imaging system, is burdensome on system resources and prone to latencies due to the size of such image data.
The literature contains many examples of methods designed to improve the quality and/or speed of tomographic image reconstruction. Recently, multiresolution methods based on hierarchical functions, especially wavelets see e.g. I. Daubechies, “Orthonormal Bases of Compactly Supported Wavelets”, Comm. Pure and Appl. Math, Vol. 41, pp. 909–996, 1988; S. G. Mallat, “A Theory for Multiresolution Signal Decomposition: the Wavelet Representation”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 11, Issue 7, pp. 674–693, 1989; and Beylkin, et al., “Fast Wavelet Transforms and Numerical Algorithms I”, Comm. Pure and Appl. Math., Vol. 44, pp. 141–183, 1991; the disclosures of which are incorporated herein by reference, have been the focus of much research. In the area of tomography, the application of wavelets falls generally into a few categories.
A first category of wavelet application in tomography is in the use of FBP algorithm. Researchers have focused on the use of wavelets with the FBP algorithm primarily with applications in the medical industry. Here the emphasis is on reducing the patient's exposure to X band radiation by constructing a “region of interest” based method that requires fewer X-ray projections to be taken. Although these methods are not truly local, by incorporating wavelet filtering into filtered back-projection, one may construct a “near-local” representation of the global Radon transform (see e.g. Rashid-Farrokhi, et al., “Wavelet-Based Multiresolution Local Tomography”, IEEE Transactions on Image Processing, Vol. 6, Issue 10, pp. 1412–1430, 1997; Olson, et al., “Wavelet Localization of the Radon Transform”, IEEE Transactions on Signal Processing, Vol. 42, Issue 8, pp. 2055–2067, 1994; DeStefano et al., “Wavelet Localization of the Radon Transform in Even Dimensions”, Time-Frequency and Time-Scale Analysis, 1992, Proceedings of the IEEE-SP International Symposium, pp. 137–140, 4–6 Oct. 1999; Warrick, et al., “A Wavelet Localized Radon Transform”, Proceedings of the SPIE—The International Society for Optical Engineering, Vol. 2569, Part 2, pp. 632–643, 1995; Warrick, et al., “A Wavelet Localized Radon Transform Based Detector for a Signal with Unknown Parameters”, Signals, Systems and Computers, Vol. 2, pp. 860–864, Oct. 30, 1995–Nov. 2, 1995; Sahiner, et al., “On the Use of Wavelets in Inverting the Radon Transform”, Nuclear Science Symposium and Medical Imaging Conference, 1992, IEEE, Vol. 2, pp. 1129–1131, 25–31 Oct. 1992; A. E. Yagle, “Region-of-Interest Tomography Using the Wavelet Transform and Angular Harmonics”, Image Processing, Proceedings, Vol 2, pp. 461–463, 23–26 Oct. 1995; and U.S. Pat. Nos. 5,953,388 and 5,841,890, the disclosures of which are incorporated herein by reference) which results in substantially smaller doses of X band radiation for the patient. These methods are not particularly useful in industrial applications, however, since there is little motivation to reduce dose levels, and because of the limited angle problem.
A second category of wavelet application in tomography is in the area of feature extraction and de-noising. As is well known in the literature, wavelets provide an excellent framework for distinguishing between signal and noise. Reconstructed image quality may be improved by using de-noising techniques comprising applying a wavelet transform and using various analysis methods to modify the data, see e.g., Bronnikov, et al., “Wavelet-Based Image Enhancement in X-ray Imaging and Tomography”, Applied Optic, Vol. 37, Issue 20, pp. 4437–4448, 1998; M. D. Harpen, “A Computer Simulation of Wavelet Noise Reduction in Computed Tomography”, Medical Physics, Vol. 26, Issue 8, pp. 1600–1606, August 1999; Lee, et al., “Wavelet Methods for Inverting the Radon Transform with Noisy Data”, IEEE Transactions on Image Processing, Vol. 10, Issue 1, pp. 79–94, January 2001; E. D. Kolaczyk, “Wavelet Shrinkage in Tomography”, Engineering in Medicine and Biology Society, Proceedings of the 16th Annual Inernational Confrerence of the IEEE, Vol. 2, pp. 1206–1207, 1994; and U.S. Pat. No. 5,461,655, the disclosures of which are incorporated herein by reference. Similarly, one may apply wavelet transforms to projections (detector images), and isolate signals or features of interest (such as edges), causing the resulting reconstruction to correspond only to those features, see e.g., Srinivasa, et al., “Detection of Edges from Projections”, IEEE Transactions on Medical Imaging, Vol. 11, Issue 1, pp. 76–80, March 1992; Warrick, et al., “Detection of Linear Features Using a Localized Radon Transform with a Wavelet Filter”, Acoustics, Speech, and Signal Processing, 1997, ICASSP-97., 1997 IEEE International Conference, Vol. 4, pp. 2769–2772, 21–24 Apr. 1997; and U.S. Pat. No. 6,078,680, the disclosures of which are incorporated herein by reference. When select features are isolated, the resulting representation may be stored efficiently in a compressed format, leading to reduced storage requirements or more efficient post-processing algorithms, see e.g., D. Gines, “LU Factorization of Non-Standard Forms and Direct Multiresolution Solvers”, Applied and Computational Harmonic Analysis, Vol. 5, Issue 2, pp. 156–201, 1998 and U.S. Pat. Nos. 5,644,662 and 6,041,135, the disclosures of which are incorporated herein by reference. These methods do not incorporate the compression of data into the reconstruction algorithm.
Another area of active research of multiresolution methods in tomography is for regularization. As noted, iterative solvers such as the Conjugate Gradient method are a potentially effective means of solving Limited-Angle Tomography problems. One drawback, however, is that the linear systems of equations are severely ill-conditioned, if not rank-deficient, causing an iterative solver to converge to a solution slowly, if at all. Regularization and preconditioning techniques accelerate proper convergence, and wavelets have been used in such schemes, see e.g., David L. Donoho, “Nonlinear Solution of Linear Inverse Problems by Wavelet-Vaguelette Decomposition”, Applied and Computational Harmonic Analysis, Vol. 2, Issue 2, pp. 101–126, April 1995; T. Olson, “Limited Angle Tomography Via Multiresolution Analysis and Oversampling”, Time-Frequency and Time-Scale Analysis, 1992, Proceedings of the IEEE-SP International Symposium, pp. 215–218, 4–6 Oct. 1992; Sahiner, et al., “Limited Angle Tomography Using Wavelets”, Nuclear Science Symposium and Medical Imaging Conference, 1993, Vol. 3, pp. 1912–1916, 31 Oct., 1993–6 Nov. 1993; W. Zhu, et al., “A Wavelet-Based Multiresolution Regularized Least Squares Reconstruction Approach for Optical Tomography”, IEEE Tansactions on Medical Imaging, Vol. 16, Issue 2, pp. 210–217, April 1997; M. Bhatia, et al., “Wavelet Based Methods for Multiscale Tomographic Reconstruction”, Engineering in Medicine and Biology Society, Proceedings, Vol. 1, pp. A2-A 3, 3–6 Nov. 1994; Natha, et al., “Wavelet Based compression and Denoising of Optical Tomography Data”, Optics Communications, Vol. 167, Issues 1–6, pp. 37–46, 15 Aug. 1999; and U.S. Pat. No. 6,351,548, the disclosures of which are incorporated herein by reference. The linear system may still be prohibitively large, however, so that it is not even possible to store a representation of the matrix, see the above referenced patent application entitled “COMPACT STORAGE OF PROJECTION MATRIX FOR X-RAY CIRCUIT BOARD INSPECTION USING SEPARABLE OPERATORS,” U.S. patent application Ser. No. 10/684,000, filed Oct. 10, 2003, U.S. Publication No. 2004/0120566, published Apr. 14, 2005.
In an industrial inspection system, it is desirable to process, reconstruct, and analyze very large amounts of limited angle projection data in real time. While currently known methods are capable of feature extraction, compression for storage, and regularization, none of them incorporate multiresolution compression into the reconstruction algorithm itself, as a means of reducing the copious amount of data that must be processed using e.g. the Conjugate Gradient method to obtain the solution to the Radon transform. Approaching this kind of method, some authors have used multiresolution decompositions as a means of solving elliptic, partial differential equations by compressing the matrix operator of such equations, see e.g., G. Beylkin, et al., “Fast Wavelet Transforms and Numerical Algorithms I”, Beylkin, Comm. Pure and appl. Math., Vol. 44, pp. 141–183, 1991 and B. Alpert, et al., “Adaptive Solution of Partial Differential Equations in Multiwavelet Bases”, Department of Applied Math, University of Colorado at Boulder, preprint 409, July 1999. The disclosures of which are incorporated herein by reference. This is not useful in tomography, however, as the projection matrix is already quite sparse. More useful, are emerging techniques for solving a linear system when the unkown coefficients are reconstructed in a compressed format. These methods, termed “adaptive”, have been demonstrated for differential equations (see e.g., A. Cohen and R. Masson, “Wavelet Methods for Second-Order Elliptic Problems, Preconditioning, and Adaptivity”, SIAM Journal on Scientific computing, Vol. 21, Number 3, pp. 1006–1026, 1999, the disclosure of which is incorporated herein by reference) but not in the context of ill-conditioned inverse problems such as tomography.
Accordingly, there is a need in the art for providing compressed storage of image data and efficiently reconstructing compressed images directly from such compressed image data.